// 1、一直分解 2、排序3、合并
function mergeSort(arr){
    if(arr.length<=1)return arr
    let middle=arr.length>>1
    let left=arr.slice(0,middle),
    right=arr.slice(middle)
    return tool(mergeSort(left),mergeSort(right))
}

function tool(left,right){
    let res=[]
    while(left.length&&right.length){
        if(left[0]>=right[0]){
            res.push(right.shift())
        }else{
            res.push(left.shift())
        }
    }
    while(left.length)res.push(left.shift())
    while(right.length)res.push(right.shift())
        return res
}
let arr1=[1,3,2,2,4,4,3,8,7]
console.log(mergeSort(arr1));